#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

EdgeNode::EdgeNode() {
    dest = -1;
    link = NULL;
}

EdgeNode::EdgeNode(int dest, EdgeNode* link) {
    this->dest = dest;
    this->link = link;
}

EdgeNode::~EdgeNode() {
}

int EdgeNode::getDest() {
    return dest;
}

EdgeNode* EdgeNode::getNext() {
    return link;
}

void EdgeNode::setDest(int dest) {
    this->dest = dest;
}

void EdgeNode::setNext(EdgeNode* link) {
    this->link = link;
}

VertexNode::VertexNode() {
    data = ' ';
    firstEdge = NULL;
}

VertexNode::VertexNode(char data, EdgeNode* firstEdge) {
    this->data = data;
    this->firstEdge =  firstEdge;
}

VertexNode::~VertexNode() {
    EdgeNode* node = firstEdge;
    while(node != NULL) {
        EdgeNode* temp = node;
        node = node->getNext();
        delete temp;
    }
}

char VertexNode::getData() {
    return data;
}

EdgeNode* VertexNode::getFirstEdge() {
    return firstEdge;
}

void VertexNode::setData(char data) {
    this->data = data;
}

void VertexNode::setFirstEdge(EdgeNode* firstEdge) {
    this->firstEdge = firstEdge;
}

void VertexNode::addEdge(int edgeEnd) {
    firstEdge = new EdgeNode(edgeEnd,firstEdge);
}

MyGraph::MyGraph() {
    nodeNum = 0;
    edgeNum = 0;
    VexList = NULL;
}

MyGraph::MyGraph(int nodeNum, int edgeNum, char* nodeList, int* edgeStartList, int* edgeEndList) {
    this->nodeNum = nodeNum;
    this->edgeNum = edgeNum;
    VexList = new VertexNode[nodeNum];
    for(int i = 0; i < nodeNum; i++)VexList[i].setData(nodeList[i]);
    for(int i = 0; i < edgeNum; i++) {
        VexList[edgeStartList[i]].addEdge(edgeEndList[i]);
        VexList[edgeEndList[i]].addEdge(edgeStartList[i]);
    }
}

MyGraph::~MyGraph() {
    delete []VexList;
}

int MyGraph::getNodeNum() {

}

int MyGraph::getEdgeNum() {

}

string MyGraph::printGraph() {
    string result = "";
    for(int i = 0; i < nodeNum; i++) {
        result += VexList[i].getData();
        result += ':';
        EdgeNode* temp = VexList[i].getFirstEdge();
        while(temp != NULL) {
            result += ' ';
            //result += VexList[temp->getDest()].getData();
            result += string(1, VexList[temp->getDest()].getData());
            temp = temp->getNext();
        }
        if(i != nodeNum-1)result += '\n';
    }
    return result;
}

int MyGraph::getFirstNeighbor(int v, int* visited) {

}

int MyGraph::getNextNeighbor(int v, int w, int* visited) {

}

void MyGraph::DFS(int v, int* visited, string& result) {
    result += VexList[v].getData();
    result += " ";
    visited[v] = 1;
    EdgeNode* w = VexList[v].getFirstEdge();
    while(w != NULL) {
        if(!visited[w->getDest()])DFS(w->getDest(),visited,result);
        w = w->getNext();
    }
}

string MyGraph::graph_DFS_Traverse() {
    int v = nodeNum;
    int* visited = new int[v];
    string result = "";
    for(int i = 0; i < v; i++)visited[i] = 0;
    for(int i = 0; i < v; i++)if(!visited[i])DFS(i,visited,result);
    delete []visited;
    return result;
}

void MyGraph::BFS(int v, int* visited, string& result) {
    queue<int> q;
    q.push(v);
    visited[v] = 1;
    while(!q.empty()) {
        int front = q.front();
        q.pop();
        result += VexList[front].getData();
        result += " ";
        EdgeNode* temp = VexList[front].getFirstEdge();
        while(temp != NULL) {
            if(!visited[temp->getDest()])q.push(temp->getDest());
            visited[temp->getDest()] = 1;
            temp = temp->getNext();
        }
    }
}

string MyGraph::graph_BFS_Traverse() {
    int v = nodeNum;
    int* visited = new int[v];
    string result = "";
    for(int i = 0; i < v; i++)visited[i] = 0;
    for(int i = 0; i < v; i++)if(!visited[i])BFS(i,visited,result);
    delete []visited;
    return result;
}
